package linkedList;

public class Josepuf {
    public static void main(String[] args) {
        /*circleSingLinkList circleSingLinkList = new circleSingLinkList();
        circleSingLinkList.add(5);
        circleSingLinkList.show();*/
        //测试约瑟夫问题
        circleSingLinkList circleSingLinkList1 = new circleSingLinkList();
        circleSingLinkList1.countBoy(1, 2, 5);
    }

    static class circleSingLinkList {
        private boy frist = null;

        public void add(int nums) {
            if (nums <= 0) {
                System.out.println("参数错误");
                return;
            }
            boy cur = null;
            for (int i = 1; i <= nums; i++) {
                boy boy = new boy(i);
                if (i == 1) {
                    frist = boy;
                    frist.setNext(frist);//构成环状
                } else {
                    cur.setNext(boy);
                    boy.setNext(frist);
                }
                cur = boy;

            }
        }

        public void show() {
            if (frist == null) {
                System.out.println("队列为空");
                return;
            }
            boy cur = frist;
            while (true) {
                System.out.printf("boy的编号%d \n", cur.getNo());
                if (cur.getNext() == frist) {
                    break;
                }
                cur = cur.getNext();
            }
        }


        /**
         * @param startNo  表示从第几个小孩开始数数
         * @param countNum 表示数几下
         * @param nums     表示最初有几个小孩在圈中
         *                 根据用户输入计算小孩出圈顺序
         */
        public void countBoy(int startNo, int countNum, int nums) {
            if (startNo < 1 || startNo > nums || nums <= 0) {
                System.out.println("参数错误");
                return;
            }
            //加入节点
            add(nums);
            //辅助指针
            boy cour = frist;
            //把辅助指针指向frist的前一个节点即环形链表的最后一个
            while (true) {
                if (cour.getNext() == frist) {//说明cur指向了最后一个小孩
                    break;
                }
                cour = cour.getNext();
            }
            //移动到开始数数的位置
            for (int i = 0; i < startNo - 1; i++) {
                frist = frist.getNext();
                cour = cour.getNext();
            }
            //开始出圈
            while (true) {
                if (cour == frist) {
                    //圈里剩最后一个了
                    break;
                }
                for (int i = 0; i < countNum - 1; i++) {
                    frist = frist.getNext();
                    cour = cour.getNext();
                }
                System.out.printf("小孩%d 出圈。\n", frist.getNo());
                frist = frist.getNext();//删除节点
                cour.setNext(frist);
            }
            System.out.printf("最后留下的小孩是%d\n", cour.getNo());
        }
    }

    static class boy {
        private int no;
        private boy next;

        public int getNo() {
            return no;
        }

        public void setNo(int no) {
            this.no = no;
        }

        public boy getNext() {
            return next;
        }

        public void setNext(boy next) {
            this.next = next;
        }

        public boy(int no) {
            this.no = no;
        }

        public boy() {
        }
    }
}
